package sort.cmp;

import sort.Sort;

/**
 * @Author: LDeng
 * @Date: 2021-03-26 13:35
 */
public class QuickSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        sort(0, array.length);
    }

    //对[begin,end) 范围的元素进行快速排序
    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        //确定轴点位置
        int mid = pivotIndex(begin, end);
        //对子序列进行快速排序
        sort(begin, mid);
        sort(mid + 1, end);
    }

    //返回[begin,end) 范围的轴点位置
    private int pivotIndex(int begin, int end) {
        //备份begin位置的元素
        E pivot = array[begin];
        //end指向最后一个元素
        end--;
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) {//右边元素>轴点元素
                    end--;
                } else {//右边元素<=轴点元素
                    //=> 将end的值拿出来覆盖begin位置的值
                    //=> begin++
                    array[begin] = array[end];
                    begin++;
                    break;//跳出循环，换方向
                }
            }
            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) {//左边元素<轴点元素
                    begin++;
                } else {
                    array[end] = array[begin];
                    end--;
                    break;//跳出循环，换方向
                }
            }
        }
        //将备份出来的轴点元素放入index的位置
        array[begin] = pivot;
        //能来到这里begin==end
        return begin;
    }
}
